package com.cd.algorithm.order.code;

/**
 * 二叉树排序
 * 理解：
 * 1. 二叉树排序是指将一棵二叉树按照某种顺序进行排序，常见的排序方式有：
 *    先序遍历：根节点->左子树->右子树
 *    中序遍历：左子树->根节点->右子树
 *    后序遍历：左子树->右子树->根节点
 *  2. 二叉树排序的基本思想是：
 *    先将二叉树按照某种遍历方式（如先序遍历）进行遍历，得到一个有序序列；
 *    然后再根据这个有序序列，将二叉树重新构造成一棵新的二叉树，这棵新的二叉树的结构与原二叉树相同，但节点的值按照原二叉树的有序序列进行排列。
 *    这样，就实现了二叉树的排序。
 * 3. 二叉树排序的步骤：
 *   1. 先序遍历二叉树，得到一个有序序列；
 *   2. 构造一棵新的二叉树，节点的值按照原二叉树的有序序列进行排列；
 *   3. 重复步骤1和步骤2，直到二叉树为空。
 * 4. 二叉树排序的时间复杂度：
 *   二叉树排序的时间复杂度取决于二叉树的高度，最坏情况下，二叉树的高度为O(nlogn)，因此，二叉树排序的时间复杂度为O(nlogn)。
 * 5. 二叉树排序的空间复杂度：
 *   二叉树排序的空间复杂度取决于二叉树的高度，最坏情况下，二叉树的高度为O(nlogn)，因此，二叉树排序的空间复杂度为O(n)。
 *
 */
public class BinaryTreeSort {
    Node root;

    // 插入节点方法
    public void insert(int key) {
        root = insertRec(root, key);
    }

    // 递归插入节点
    private Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        return root;
    }

    // 中序遍历打印排序结果
    public void inorderTraversal() {
        inorderRec(root);
    }

    // 递归中序遍历
    private void inorderRec(Node node) {
        if (node != null) {
            inorderRec(node.left);
            System.out.print(node.data + " "); // 打印节点值
            inorderRec(node.right);
        }
    }

    // 测试代码
    public static void main(String[] args) {
        BinaryTreeSort tree = new BinaryTreeSort();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Inorder traversal of the constructed BST:");
        tree.inorderTraversal();  // 输出排序后的序列
    }

    public static class Node {
        int data;
        Node left, right;

        public Node(int item) {
            data = item;
            left = right = null;
        }
    }
}
